#include "headfiles.h"

using namespace std;

void maxSlidingWindow(int *a, int n, int w, int *b) {
    if (a == NULL ||
        b == NULL ||
        w > n) {
        cout << "Invalid input!" << endl;
        return;
    }

    deque<int> dq;
    int i;

    for (i = 0; i < w; i++) {
        while (!dq.empty() && a[i] > a[dq.front()]) {
            dq.pop_front();
        }
        dq.push_back(i);
    }

    for (i = w; i < n; i++) {
        b[i - w] = a[dq.front()];
        
        // remove elements less than a[i] in the back
        while (!dq.empty() && a[i] > a[dq.back()]) {
            dq.pop_back();
        }

        // remove elements out of window
        while (!dq.empty() && i - dq.front() >= w) {
            dq.pop_front();
        }

        dq.push_back(i);
    }

    return;
}

/*
typedef pair<int, int> Pair;
void maxSlidingWindow(int *a, int n, int w, int *b) {
    priority_queue<Pair> q;
    for (int i = 0; i < w; i++) {
        q.push(Pair(a[i], i));
    }

    for (int i = w; i < n; i++) {
        Pair p = q.top();
        b[i - w] = p.first;

        while (p.second <= i - w) {
            q.pop();
            p = q.top();
        }
        q.push(Pair(a[i], i));
    }

    b[n - w] = q.top().first;
}
*/
/*
void maxSlidingWindow(int *a, int n, int w, int *b) {
    deque<int> q;
    int i;

    // configure the first window
    for (i = 0; i < w; i++) {
        while (!q.empty() && a[i] > a[q.back()]) {
            q.pop_back();
        }
        q.push_back(i);
    }

    // Consstruct the output array b
    for (i = w; i < n; i++) {
        b[i - w] = a[q.front()];

        // remove elements less than a[i] from the queue
        while (!q.empty() && a[i] > a[q.back()]) {
            q.pop_back();
        }

        // remove elements out of the window from the queue
        while (!q.empty() && q.front() <= i - w) {
            q.pop_front();
        }
        q.push_back(i);
    }
    b[n - w] = a[q.front()];
}
*/
